CoCalc Logo Icon
DocsShareSupport News Sign UpSign In
Views: 87
Image: ubuntu2004
Embed | Download | Raw |
Kernel: Python 3 (ipykernel)
import random from IPython.core.display import SVG import pyomo.environ as pyo from pysat.solvers import Solver from pysat.formula import CNF import py_svg_combinatorics as psc from ipywidgets import widgets, HBox from collections import Counter from pprint import pprint from random import randint import numpy as np from IPython.display import IFrame import IPython from copy import copy import os from pathlib import Path nbname = '' try: nbname = __vsc_ipynb_file__ except: if 'COCALC_JUPYTER_FILENAME' in os.environ: nbname = os.environ['COCALC_JUPYTER_FILENAME'] title_ = Path(nbname).stem.replace('-', '_').title() IFrame(f'https://discopal.ispras.ru/index.php?title=Hardprob/{title_}&useskin=cleanmonobook', width=1280, height=300)

Генератор случайных данных

def get_random_k_choice_knapsack(m, n): B = np.random.randint(n*3, n*10) # предметы не влезающие в рюкзак сразу не берем A = np.random.randint(1, B, size=(m, n)) C = np.random.randint(1, 10*B, size=(m, n)) return A, C, B A, C, B = get_random_k_choice_knapsack(3, 10) A, C, B
(array([[22, 11, 16, 13, 5, 33, 27, 9, 4, 31], [ 4, 5, 19, 26, 27, 7, 27, 23, 20, 36], [ 5, 23, 15, 33, 5, 17, 26, 5, 27, 30]]), array([[ 93, 228, 243, 288, 377, 40, 196, 224, 80, 161], [337, 48, 245, 317, 361, 131, 332, 125, 182, 107], [176, 1, 117, 32, 353, 256, 233, 320, 302, 330]]), 38)
def get_model(A, C, B): m = pyo.ConcreteModel() m.m, m.n = A.shape # на всякий случай, возьмем с собой m.A = A m.C = C m.B = B m.J = range(m.n) m.I = range(m.m) m.x = pyo.Var(m.J, domain=pyo.Binary) m.y = pyo.Var(m.I, m.J, domain=pyo.Binary) @m.Constraint(m.J) def для_каждой_колонки_выбираем_только_одну_строку(m, j): return sum(m.y[... ,j]) == m.x[j] m.f = pyo.Var(m.J, domain=pyo.NonNegativeIntegers) @m.Constraint(m.J) def конвертируем_выбор_в_номер(m, j): return sum(i * m.y[i ,j] for i in m.I) == m.f[j] m.obj = pyo.Objective(expr = sum( m.C[i, j] * m.y[i, j] for i in m.I for j in m.J), sense=pyo.maximize) @m.Constraint(m.I) def влезает_в_рюкзак(m, i): return sum(A[i, j] * m.y[i, j] for j in m.J) <= B return m m = get_model(A, C, B) m.pprint()
8 Set Declarations f_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 10 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} x_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 10 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} y_index : Size=1, Index=None, Ordered=True Key : Dimen : Domain : Size : Members None : 2 : y_index_0*y_index_1 : 30 : {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9)} y_index_0 : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 3 : {0, 1, 2} y_index_1 : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 10 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} влезает_в_рюкзак_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 3 : {0, 1, 2} для_каждой_колонки_выбираем_только_одну_строку_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 10 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} конвертируем_выбор_в_номер_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 10 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 3 Var Declarations f : Size=10, Index=f_index Key : Lower : Value : Upper : Fixed : Stale : Domain 0 : 0 : None : None : False : True : NonNegativeIntegers 1 : 0 : None : None : False : True : NonNegativeIntegers 2 : 0 : None : None : False : True : NonNegativeIntegers 3 : 0 : None : None : False : True : NonNegativeIntegers 4 : 0 : None : None : False : True : NonNegativeIntegers 5 : 0 : None : None : False : True : NonNegativeIntegers 6 : 0 : None : None : False : True : NonNegativeIntegers 7 : 0 : None : None : False : True : NonNegativeIntegers 8 : 0 : None : None : False : True : NonNegativeIntegers 9 : 0 : None : None : False : True : NonNegativeIntegers x : Size=10, Index=x_index Key : Lower : Value : Upper : Fixed : Stale : Domain 0 : 0 : None : 1 : False : True : Binary 1 : 0 : None : 1 : False : True : Binary 2 : 0 : None : 1 : False : True : Binary 3 : 0 : None : 1 : False : True : Binary 4 : 0 : None : 1 : False : True : Binary 5 : 0 : None : 1 : False : True : Binary 6 : 0 : None : 1 : False : True : Binary 7 : 0 : None : 1 : False : True : Binary 8 : 0 : None : 1 : False : True : Binary 9 : 0 : None : 1 : False : True : Binary y : Size=30, Index=y_index Key : Lower : Value : Upper : Fixed : Stale : Domain (0, 0) : 0 : None : 1 : False : True : Binary (0, 1) : 0 : None : 1 : False : True : Binary (0, 2) : 0 : None : 1 : False : True : Binary (0, 3) : 0 : None : 1 : False : True : Binary (0, 4) : 0 : None : 1 : False : True : Binary (0, 5) : 0 : None : 1 : False : True : Binary (0, 6) : 0 : None : 1 : False : True : Binary (0, 7) : 0 : None : 1 : False : True : Binary (0, 8) : 0 : None : 1 : False : True : Binary (0, 9) : 0 : None : 1 : False : True : Binary (1, 0) : 0 : None : 1 : False : True : Binary (1, 1) : 0 : None : 1 : False : True : Binary (1, 2) : 0 : None : 1 : False : True : Binary (1, 3) : 0 : None : 1 : False : True : Binary (1, 4) : 0 : None : 1 : False : True : Binary (1, 5) : 0 : None : 1 : False : True : Binary (1, 6) : 0 : None : 1 : False : True : Binary (1, 7) : 0 : None : 1 : False : True : Binary (1, 8) : 0 : None : 1 : False : True : Binary (1, 9) : 0 : None : 1 : False : True : Binary (2, 0) : 0 : None : 1 : False : True : Binary (2, 1) : 0 : None : 1 : False : True : Binary (2, 2) : 0 : None : 1 : False : True : Binary (2, 3) : 0 : None : 1 : False : True : Binary (2, 4) : 0 : None : 1 : False : True : Binary (2, 5) : 0 : None : 1 : False : True : Binary (2, 6) : 0 : None : 1 : False : True : Binary (2, 7) : 0 : None : 1 : False : True : Binary (2, 8) : 0 : None : 1 : False : True : Binary (2, 9) : 0 : None : 1 : False : True : Binary 1 Objective Declarations obj : Size=1, Index=None, Active=True Key : Active : Sense : Expression None : True : maximize : 93*y[0,0] + 228*y[0,1] + 243*y[0,2] + 288*y[0,3] + 377*y[0,4] + 40*y[0,5] + 196*y[0,6] + 224*y[0,7] + 80*y[0,8] + 161*y[0,9] + 337*y[1,0] + 48*y[1,1] + 245*y[1,2] + 317*y[1,3] + 361*y[1,4] + 131*y[1,5] + 332*y[1,6] + 125*y[1,7] + 182*y[1,8] + 107*y[1,9] + 176*y[2,0] + y[2,1] + 117*y[2,2] + 32*y[2,3] + 353*y[2,4] + 256*y[2,5] + 233*y[2,6] + 320*y[2,7] + 302*y[2,8] + 330*y[2,9] 3 Constraint Declarations влезает_в_рюкзак : Size=3, Index=влезает_в_рюкзак_index, Active=True Key : Lower : Body : Upper : Active 0 : -Inf : 22*y[0,0] + 11*y[0,1] + 16*y[0,2] + 13*y[0,3] + 5*y[0,4] + 33*y[0,5] + 27*y[0,6] + 9*y[0,7] + 4*y[0,8] + 31*y[0,9] : 38.0 : True 1 : -Inf : 4*y[1,0] + 5*y[1,1] + 19*y[1,2] + 26*y[1,3] + 27*y[1,4] + 7*y[1,5] + 27*y[1,6] + 23*y[1,7] + 20*y[1,8] + 36*y[1,9] : 38.0 : True 2 : -Inf : 5*y[2,0] + 23*y[2,1] + 15*y[2,2] + 33*y[2,3] + 5*y[2,4] + 17*y[2,5] + 26*y[2,6] + 5*y[2,7] + 27*y[2,8] + 30*y[2,9] : 38.0 : True для_каждой_колонки_выбираем_только_одну_строку : Size=10, Index=для_каждой_колонки_выбираем_только_одну_строку_index, Active=True Key : Lower : Body : Upper : Active 0 : 0.0 : y[0,0] + y[1,0] + y[2,0] - x[0] : 0.0 : True 1 : 0.0 : y[0,1] + y[1,1] + y[2,1] - x[1] : 0.0 : True 2 : 0.0 : y[0,2] + y[1,2] + y[2,2] - x[2] : 0.0 : True 3 : 0.0 : y[0,3] + y[1,3] + y[2,3] - x[3] : 0.0 : True 4 : 0.0 : y[0,4] + y[1,4] + y[2,4] - x[4] : 0.0 : True 5 : 0.0 : y[0,5] + y[1,5] + y[2,5] - x[5] : 0.0 : True 6 : 0.0 : y[0,6] + y[1,6] + y[2,6] - x[6] : 0.0 : True 7 : 0.0 : y[0,7] + y[1,7] + y[2,7] - x[7] : 0.0 : True 8 : 0.0 : y[0,8] + y[1,8] + y[2,8] - x[8] : 0.0 : True 9 : 0.0 : y[0,9] + y[1,9] + y[2,9] - x[9] : 0.0 : True конвертируем_выбор_в_номер : Size=10, Index=конвертируем_выбор_в_номер_index, Active=True Key : Lower : Body : Upper : Active 0 : 0.0 : 0*y[0,0] + y[1,0] + 2*y[2,0] - f[0] : 0.0 : True 1 : 0.0 : 0*y[0,1] + y[1,1] + 2*y[2,1] - f[1] : 0.0 : True 2 : 0.0 : 0*y[0,2] + y[1,2] + 2*y[2,2] - f[2] : 0.0 : True 3 : 0.0 : 0*y[0,3] + y[1,3] + 2*y[2,3] - f[3] : 0.0 : True 4 : 0.0 : 0*y[0,4] + y[1,4] + 2*y[2,4] - f[4] : 0.0 : True 5 : 0.0 : 0*y[0,5] + y[1,5] + 2*y[2,5] - f[5] : 0.0 : True 6 : 0.0 : 0*y[0,6] + y[1,6] + 2*y[2,6] - f[6] : 0.0 : True 7 : 0.0 : 0*y[0,7] + y[1,7] + 2*y[2,7] - f[7] : 0.0 : True 8 : 0.0 : 0*y[0,8] + y[1,8] + 2*y[2,8] - f[8] : 0.0 : True 9 : 0.0 : 0*y[0,9] + y[1,9] + 2*y[2,9] - f[9] : 0.0 : True 15 Declarations: x_index x y_index_0 y_index_1 y_index y для_каждой_колонки_выбираем_только_одну_строку_index для_каждой_колонки_выбираем_только_одну_строку f_index f конвертируем_выбор_в_номер_index конвертируем_выбор_в_номер obj влезает_в_рюкзак_index влезает_в_рюкзак
solver = pyo.SolverFactory('cbc') solver.solve(m).write() m.x.extract_values(), m.f.extract_values()
# ========================================================== # = Solver Results = # ========================================================== # ---------------------------------------------------------- # Problem Information # ---------------------------------------------------------- Problem: - Name: unknown Lower bound: 2438.0 Upper bound: 2438.0 Number of objectives: 1 Number of constraints: 13 Number of variables: 30 Number of binary variables: 40 Number of integer variables: 50 Number of nonzeros: 30 Sense: maximize # ---------------------------------------------------------- # Solver Information # ---------------------------------------------------------- Solver: - Status: ok User time: -1.0 System time: 0.52 Wallclock time: 0.29 Termination condition: optimal Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available. Statistics: Branch and bound: Number of bounded subproblems: 0 Number of created subproblems: 0 Black box: Number of iterations: 5 Error rc: 0 Time: 0.45127415657043457 # ---------------------------------------------------------- # Solution Information # ---------------------------------------------------------- Solution: - number of solutions: 0 number of solutions displayed: 0
({0: 1.0, 1: 0.0, 2: 1.0, 3: 1.0, 4: 1.0, 5: 1.0, 6: 1.0, 7: 1.0, 8: 1.0, 9: 1.0}, {0: 1.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0, 5: 1.0, 6: 1.0, 7: 2.0, 8: 0.0, 9: 2.0})